/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年11月04日
*   描    述：
*   
================================================================*/


#include <iostream>

using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int> > path(m, vector<int> (n, 0));
        if( m == 0 || n == 0 || obstacleGrid[0][0] || obstacleGrid[m-1][n-1])
           return 0;

        if( m==1 && n==1 )
            return 1;

        path[m-1][n-1] = 1;
        int i = m - 2;
        for(i; i >=0; i--){
            if( !obstacleGrid[i][n-1] )
                path[i][n-1] = path[i+1][n-1];
        }

        int j = n - 2;
        for(j; j >= 0; j--){
            if( !obstacleGrid[m-1][j] )
                path[m-1][j] = path[m-1][j+1];
        }

        for( i = m - 2; i >= 0; i-- ){
            for(j = n - 2; j >= 0; j--){
                if( !obstacleGrid[i][j] )
                    path[i][j] = path[i+1][j] + path[i][j+1];
            }
        }

        return path[0][0];
    }
};
